package org.xingole.daily;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 
 * @since 3/26/2025
 */
public class FindMissingAndRepeatedValues {
     /**
      * 
      * @param grid 0-indexed 2D integer matrix grid of size n * n with value
      * in the range [1, n^2].
      * @return a 0-indexed interger array ans of size 2 where ans[0] 
      * equals to a and ans[1] to b.
      */
     public int[] findMissingAndRepeatedValues(int[][] grid) {
          int n = grid.length;
          int missing = -1, repeat = -1;

          // Store frequency of each number in the grid
          var freq = new HashMap<Integer, Integer>();
          for ( int[] row : grid ) {
               for ( int num : row ) {
                    freq.put(
                         num, 
                         freq.getOrDefault(num, 0) + 1
                    );
               }
          }

          // Check numbers from 1 to n^2 to find missing and repeated values.
          for ( int num = 1; num <= n * n ; num++ ) {
               if ( !freq.containsKey(num) ) {
                    missing = num;   // Number not present in grid
               } else if ( freq.get(num) == 2 ) {
                    repeat = num;    // Number appears twice
               }
          }

          return new int[]{ repeat, missing };
     }

     public static void main(String[] args) {
          FindMissingAndRepeatedValues finder = new FindMissingAndRepeatedValues();

          int[][] grid;

          // Example 1:
          // Input: grid = [[1, 3], [2, 2]]
          // Output: [2, 4]
          grid = new int[][]{{1, 3}, {2, 2}};
          System.out.println("Exmaple 1 Output: " + 
               Arrays.toString(finder.findMissingAndRepeatedValues(grid) )
          );


     }
}
